#ifndef _HASH_H_
#define _HASH_H_

#include "types.h"
#include "string.h"
#include "os_mem.h"
#include "os_io.h"
#include "err.h"

typedef enum
{
  HASH_TYPE_NUMERIC,
  HASH_TYPE_STRING
}hash_type_t;

typedef struct hash_node_t
{
    union {
        uint8_t *name;
	uint32_t value;
    }key;
    
    uint32_t value;

    struct hash_node_t *next;
    struct hash_node_t *prev;
}hash_node_t;

typedef struct
{
   uint16_t num_entries;
   hash_node_t sentinel;
}hash_bucket_t;
    

typedef struct 
{
    uint16_t num_buckets;
    hash_type_t hash_type;
    hash_bucket_t *buckets;
}hash_t;



static inline uint16_t hash_name(const uint8_t *name, uint16_t size)
{
    uint32_t rand_num = 0xA5A5A5A5;

    while (*name) {
        rand_num += *name++;
    }

    return (rand_num & (size - 1));
}

static inline uint16_t hash_value(const uint32_t key, uint16_t size)
{
    return (key & (size - 1));
}

static uint16_t hash(const void *key, uint16_t size, hash_type_t hash_type)
{
    if (hash_type == HASH_TYPE_STRING) {
        return hash_name((const uint8_t *)key, size);
    } else {
        return hash_value((const uint32_t)(*(const uint32_t *)key), size);
    }
}



static inline err_t remove_hash_node(hash_t *hash_ptr, const void *key)
{
    uint16_t index = 0;
    hash_bucket_t *bucket;
    hash_node_t *cur_node;
    uint8_t found = 0;
 
    if (!hash_ptr || !key) { printf("Invalid hash_ptr/key in remove_node\n"); return ERR_INVALID; }

    index = hash(key, hash_ptr->num_buckets, hash_ptr->hash_type);
    bucket = &hash_ptr->buckets[index];

    index = bucket->num_entries;
    cur_node = bucket->sentinel.next;
    while(cur_node) {

        found = 0;
        if (hash_ptr->hash_type == HASH_TYPE_STRING) {
	    if (!strcmp(cur_node->key.name, (uint8_t *)key)) {
	        found = 1;
		free(cur_node->key.name);
	    }
	} else {
	    if (cur_node->key.value == *(uint32_t *)key) {
	        found = 1;
	    }
	}

	if (found) {
	    
	    cur_node->prev->next = cur_node->next;
	    
	    if (cur_node->next) {
	        cur_node->next->prev = cur_node->prev;
	    } else {
	        // We were the last node
		// Update the tail
		bucket->sentinel.prev = cur_node->prev;
	    }

	    free((uint8_t *)cur_node);
	    return ERR_SUCCESS;
	}
	cur_node = cur_node->next;
    }

    // not found
    printf("Hash node not found while remove\n");
    return ERR_NOT_FOUND;
}

static inline err_t destroy_hash(hash_t *hash_ptr)
{
    uint16_t index = 0;
    hash_bucket_t *bucket;
    hash_node_t *cur_node;

    if (!hash_ptr) { printf("Invalid hash ptr while destroy\n"); return ERR_INVALID; }

    for (index = 0; index < hash_ptr->num_buckets; index++) {
     
        bucket = &hash_ptr->buckets[index];
	cur_node = bucket->sentinel.next;
	while (cur_node) {
	    bucket->sentinel.next = cur_node->next;
	    if (hash_ptr->hash_type == HASH_TYPE_STRING) {
	        free((uint8_t *)cur_node->key.name);
	    }
	    free(cur_node);
	    cur_node = bucket->sentinel.next;
	}
    }
    free((uint8_t *)hash_ptr->buckets);
    return ERR_SUCCESS;
}

static inline err_t lookup_hash(hash_t *hash_ptr, const void *key, uint32_t *value)
{
    uint16_t index = 0;
    hash_bucket_t *bucket;
    hash_node_t *cur_node;
 
    if (!hash_ptr || !key) { printf("Invalid hash ptr/key while lookup\n"); return ERR_INVALID; }

    index = hash(key, hash_ptr->num_buckets, hash_ptr->hash_type);
    bucket = &hash_ptr->buckets[index];

    index = bucket->num_entries;
    cur_node = bucket->sentinel.next;
    while(cur_node) {
        if (hash_ptr->hash_type == HASH_TYPE_STRING && !strcmp(cur_node->key.name, key)) {
	    *value = cur_node->value;
	    return ERR_SUCCESS;
	} else if (hash_ptr->hash_type == HASH_TYPE_NUMERIC && cur_node->key.value == *(uint32_t *)key) {
	    *value = cur_node->value;
	    return ERR_SUCCESS;
	}
	cur_node = cur_node->next;
    }

    // not found
    //printf("Hash key/value not found while lookup\n");
    return ERR_NOT_FOUND;
}


static inline err_t insert_hash(hash_t *hash_ptr, const void *key, uint32_t value)
{
    uint16_t index = 0;
    hash_bucket_t *bucket;
    hash_node_t *cur_node;
    uint8_t *new_name;
 
    if (!hash_ptr || !key) { printf("Invalid hash ptr/key while insert\n"); return ERR_INVALID; }

    index = hash(key, hash_ptr->num_buckets, hash_ptr->hash_type);
    bucket = &hash_ptr->buckets[index];

    index = bucket->num_entries;
    cur_node = bucket->sentinel.next;
    while(cur_node) {
        if ((hash_ptr->hash_type == HASH_TYPE_STRING && !strcmp(cur_node->key.name, (uint8_t *)key)) ||
	    (hash_ptr->hash_type == HASH_TYPE_NUMERIC && cur_node->key.value == *(uint32_t *)key)) {
	    cur_node->value = value;   // update old value
	    return ERR_ALREADY_EXIST;
	}
	cur_node = cur_node->next;
    }

    cur_node = (hash_node_t *)calloc(1, sizeof(hash_node_t));
    if (cur_node) {
        if (hash_ptr->hash_type == HASH_TYPE_STRING) {
	    new_name = calloc(1, strlen((uint8_t *)key) + 1);
            if (!new_name) {
	        free(cur_node);
		printf("Hash out of mem while insert\n");
		return ERR_NO_MEM;
	    }
	    strcpy(new_name, (uint8_t *)key);
	    cur_node->key.name = new_name;
	} else {
	    cur_node->key.value = *(uint32_t *)key;
	}

	cur_node->value = value;
        bucket->sentinel.prev->next = cur_node;
	cur_node->next = NULL;
	cur_node->prev = bucket->sentinel.prev;
	bucket->sentinel.prev = cur_node;
    } else {
        printf("Hash out of mem while insert\n");
        return ERR_NO_MEM;
    }
        
    return ERR_SUCCESS;
}


static inline err_t create_hash(hash_t *hash_ptr, uint16_t size, hash_type_t hash_type)
{
     uint16_t i = 0;

     if (size == 0) { printf("Invalid size while hash create\n"); return ERR_INVALID; }
     if ((size) & (size - 1)) { printf("Invalid size bits while hash create\n"); return ERR_INVALID; }
     if (hash_ptr == NULL) { printf("Invalid hash ptr while create\n"); return ERR_INVALID; }

     hash_ptr->buckets = (hash_bucket_t *)calloc(size, sizeof(hash_bucket_t));
     if (hash_ptr->buckets == NULL) { printf("Out of memory while creating hash\n"); return ERR_NO_MEM; }

     hash_ptr->num_buckets = size;
     hash_ptr->hash_type = hash_type;

     for (i = 0; i < size; i++) {
         hash_ptr->buckets[i].sentinel.prev = &hash_ptr->buckets[i].sentinel;
     }

     return ERR_SUCCESS;
 }

#endif
